/* George Siegle
 * z863j283
 * HW 5 question 1
 */

/*Sudo-Code**********************************
 * main()
 * insert data into an array.
 * Sort array using insertions sort in a for loop.
 * Insert array into structure head and print each item of head with printSSLL function in a for loop.
 * Free head.
 * 
 * insertSSLL(node *head, int x)
 * Initialize a temperary structure, tmpCell, of type node * to hold items of head.
 * Set tmpCell equal to head.
 * Allocate memory for tmpCell->next.
 * Set tmpCell->next->key equal to x.
 * Return tmpCell.
 * 
 * printfSSLL(node *head, int countIndex)
 * Print head->next->key to terminal.
 */

#include <stdio.h>
#include <stdlib.h>

#define ARRAYSIZE 10 /* number to represent the number of integers going to be stored in an array */

struct linked_list
{
  int key; // Element to hold integer value of linked_list.
  struct linked_list *next; // Pointer to advance in linked_list.
};
typedef struct linked_list node;
node *insertSSLL(node *head, int x);
void printSSLL(node *head, int countIndex);

int main()
{
  node *head;
  head = (node *)malloc(sizeof(node *));
  int arrayOfNumbers[ARRAYSIZE] = {5, 9, 3, 1, 2, 4, 6, 7, 8};
  int countArrayIndex;
  int sortHold;
  int currentArrayIndex;
  int walkThroughArray;
  int firstArrayIndex = 0;
  int lastArrayIndex = ARRAYSIZE;
  
  // Perform insertion sort on arrayOfNumbers to order arrayOfNumbers in ascending order
  for(currentArrayIndex = firstArrayIndex + 1; currentArrayIndex <= lastArrayIndex; currentArrayIndex++)
  {
    sortHold = arrayOfNumbers[currentArrayIndex];
    walkThroughArray = currentArrayIndex - 1;
    while(walkThroughArray >= firstArrayIndex && sortHold < arrayOfNumbers[walkThroughArray])
    {
      arrayOfNumbers[walkThroughArray + 1] = arrayOfNumbers[walkThroughArray];
      walkThroughArray = walkThroughArray - 1;
    }
    arrayOfNumbers[walkThroughArray + 1] = sortHold;
  }
    
  
  for(countArrayIndex = 1; countArrayIndex < ARRAYSIZE; countArrayIndex++)
  {
    // Insert each integer in arrayOfNumbers in structure head
    head = insertSSLL(head, arrayOfNumbers[countArrayIndex]);
    printSSLL(head, countArrayIndex);
    
    // Advance head to next pointer
    head = head->next;
  }
  free(head);
  exit(0);
}

// This function inserts an integer value x into the structure tmpCell which is used to insert the values of x into the structure head
node *insertSSLL(node *head, int x)
{
  node *tmpCell;
  tmpCell = (node *)malloc(sizeof(node *));
  tmpCell = head;
  
  tmpCell->next = malloc(sizeof(node *));
  tmpCell->next->key = x;

  return(tmpCell);
}

// This function prints each value inside the structure head
void printSSLL(node *head, int countIndex)
{
    printf("Item %d in the structure is %d\n", countIndex, head->next->key);
}